Numbers with same consecutive differences [Brute Force]

Time: O(2^N); Space: O(2^N); medium

Return all non-negative integers of length N such that the absolute difference between every two consecutive digits is K.

Note that every number in the answer must not have leading zeros except for the number 0 itself. For example, 01 has one leading zero and is invalid, but 0 is valid.

You may return the answer in any order.

Example 1:

Input: N = 3, K = 7

Output: [181,292,707,818,929]

Explanation:

  • Note that 070 is not a valid number, because it has leading zeroes.

Example 2:

Input: N = 2, K = 1

Output: [10,12,21,23,32,34,43,45,54,56,65,67,76,78,87,89,98]

Note:

  • 1 <= N <= 9

  • 0 <= K <= 9

1. Brute Force

Intuition Let’s try to write some number in the answer digit by digit.

For each digit except the first, there are at most 2 choices for that digit. This means that there are at most 9 * 2^8 possible 9 digit numbers, for example. This is small enough to brute force.

Algorithm An N digit number is just an N-1 digit number with a final digit added. If the N−1 digit number ends in a digit d, then the N digit number will end in d−K or d+K (provided these are digits in the range [0,9]). We store these numbers in a Set structure to avoid duplicates.

Also, we should be careful about leading zeroes – only 1 digit numbers will start with 0.

[13]:

class Solution1(object):
    """
    Time: O(2^N).
    Space: O(2^N).
    """
    def numsSameConsecDiff(self, N, K):
        """
        :type N: int
        :type K: int
        :rtype: List[int]
        """
        ans = {x for x in range(1, 10)}
        for _ in range(N-1):
            ans2 = set()
            for x in ans:
                d = x % 10
                if d - K >= 0:
                    ans2.add(10*x + d-K)
                if d + K <= 9:
                    ans2.add(10*x + d+K)
            ans = ans2

        if N == 1:
            ans.add(0)

        return list(ans)

[21]:

s = Solution1()
N = 3
K = 7
result = s.numsSameConsecDiff(N, K)
result.sort()
assert result == [181,292,707,818,929]

N = 2
K = 1
result = s.numsSameConsecDiff(N, K)
result.sort()
assert result == [10,12,21,23,32,34,43,45,54,56,65,67,76,78,87,89,98]

[26]:

class Solution2(object):
    """
    Time:  O(2^N)
    Space: O(2^N)
    """
    def numsSameConsecDiff(self, N, K):
        """
        :type N: int
        :type K: int
        :rtype: List[int]
        """
        curr = range(10)
        for _ in range(N-1):
            curr = [x*10 + y for x in curr for y in set([x%10 + K, x%10 - K])
                    if x and 0 <= y < 10]
        return curr

[27]:

s = Solution2()
N = 3
K = 7
result = s.numsSameConsecDiff(N, K)
result.sort()
assert result == [181,292,707,818,929]

N = 2
K = 1
result = s.numsSameConsecDiff(N, K)
result.sort()
assert result == [10,12,21,23,32,34,43,45,54,56,65,67,76,78,87,89,98]